package Search;
/**
 * LGSearch is used to perform a pattern match on a directed labelled graph
 * @author Darren
 */
import java.util.Vector;
import java.util.ArrayList;
import java.util.HashSet;

import Common.Graph;
import Common.Pattern;

public class LGSearchFindAll {

	private Pattern pattern;
	private Graph graph;
	/**
	 * Constructor for LGSearch
	 *
	 * @param p the pattern to find
	 * @param g the graph to find the pattern within
	 */
	public LGSearchFindAll(Pattern p, Graph g) {
		pattern = p;
		graph = g;
	}

	/**
	 *  Can all the symbols in the pattern be reached from a particular
	 *  vertex regardless of order and number of occurrences.
	 *  NOTE that nodes can be visited multiple times.
	 *
	 * @param g 2D matrix representation of the graph
	 * @param numVertices the number of vertices in the graph
	 * @param startVertex the vector to start searching from
	 * @return True - if all the symbols in the pattern can be reached
	 * 		   False - otherwise
	 */
	public boolean patternReachable(int[][] g, int numVertices, int startVertex) {

		// A queue for storing visited nodes in
		Vector<Integer> Q = new Vector<Integer>();

		// Find a set of symbols in the pattern
		HashSet<String> patternSymbolSet = new HashSet<String>(this.pattern.symbolSet());

		// Remove the first symbol from the pattern
		patternSymbolSet.remove(graph.getLabelAt(startVertex));

		// Queue markers
		int QHead = 0;
		int pushPos = 0;

		// Push a node with the first symbol in the pattern
		// on to the tail of the queue
		Q.add(pushPos, startVertex);
		pushPos++;

		// while there are connected unexplored nodes and pattern symbols to find
		while (QHead != pushPos && QHead <= numVertices - 1 && patternSymbolSet.size() > 0) {

			// Pop the next vertex from the head of the queue
			int curNode = Q.get(QHead);
			QHead++;

			// for each node adjacent to this node and there are pattern symbols to find
			for (int adjNode = 0; adjNode < numVertices && patternSymbolSet.size() > 0; adjNode++) {

				// For each vertex x adjacent to w
				if (g[curNode][adjNode] == 1) {

                    // Is the label at this node within the pattern
					if (patternSymbolSet.contains(graph.getLabelAt(adjNode))) {

                   		patternSymbolSet.remove(graph.getLabelAt(adjNode));
                   	}

					if (!Q.contains(adjNode)) {
						// Push x on to the tail of Q
						Q.add(pushPos, adjNode);
						pushPos++;
					}
				}
			}
		}
		// If the symbol set is empty all the symbols in the pattern can be reached
		return patternSymbolSet.size() == 0;
	}

	/**
	 * Traverse the graph looking for the symbols in the pattern in the order
	 * they appear in the pattern
	 *
	 * @param g a 2D representation of the graph
	 * @param numVertices the number of vertices in the graph
	 * @param curNode the index of the vertex to look from
	 * @param patternIndex the index of the symbol in the pattern to find
	 * @param seq the sequence of nodes to visit to traverse the graph in pattern order
	 * @param seqLen the length of the sequence, used for determining when the sequence has been found
	 * @param seqAllFromNode all the sequences of nodes to visit in order to traverse the graph in pattern order
	 */
	public void findOrderedPatternSymbols(int[][] g, int numVertices, int curNode, int patternIndex, int seq[], int seqLen, Vector<int[]> seqAllFromNode) {

		// Have we found every symbol in the pattern
		if (patternIndex < seqLen) {

			// While the sequence has not been found
			// For every node adjacent to the current node is it's label equal to the next symbol in the pattern
			for (int adjNode = 0; adjNode < numVertices; adjNode++) {

				// Is the current node adjacent to this node
				if (g[curNode][adjNode] == 1) {

					// Does this node have the label we are looking for
					if (this.graph.getLabelAt(adjNode).equals(this.pattern.elementAt(patternIndex))) {

						// Update the sequence of nodes to traverse
						seq[patternIndex] = adjNode;
						// Has the entire pattern been found
						if (patternIndex == seqLen -1) {
							// Add the new sequence to the list of all sequences from this node
							seqAllFromNode.add(seq.clone());
						}
						// Recursively look for a node that has the next label in the pattern from the adjacent node
						findOrderedPatternSymbols(g, numVertices, adjNode, patternIndex+1, seq, seqLen, seqAllFromNode);
					}
				}
			}
		}
	}

    /**
     * Search the graph for the given pattern
     * @return all the sequences that satisfy the pattern
     */
	public Vector<int[]> Search() {

		int patternIndex = 0;
		// Find a list of nodes that have the first symbol in the pattern
		ArrayList<Integer> nodes = this.graph.getIndexOf(this.pattern.elementAt(patternIndex));

		// The sequence of nodes to traverse is equal in length to the pattern
		int seqLen = this.pattern.length();

		// Create a 2D representation of the graph for searching
		int[][] g = graph.getEdgeMatrix();
		int numVertices = graph.getNumberOfVertices();

		// A vector of all the sequences within the graph
		Vector<int []> seqAllInGraph = new Vector<int []>();

		// Loop through the nodes that have the first symbol in the pattern
		for (int i = 0; i < nodes.size(); i++) {

			int startVertex = nodes.get(i);
			// From a node with the first symbol in the pattern can
			// other nodes with all the symbols in the pattern be reached
			if (patternReachable(g, numVertices, startVertex)) {

				// The index in the pattern to look from
				patternIndex = 0;
				// A vector of all the sequences from this starting nodes
				Vector<int []> seqAllFromNode = new Vector<int []>();
				// The sequence of nodes in the graph to traverse
				int[] seq = new int[seqLen];
				seq[patternIndex] = startVertex;
				// The remainder of the sequence is unknown
				for (int j = 1; j < seqLen; j++) {
					seq[j] = -1;
				}
				// Can all the symbols in the pattern be reached from this node in the correct order
				findOrderedPatternSymbols(g, numVertices, startVertex, patternIndex+1, seq, seqLen, seqAllFromNode);

				// Check for success when at least one sequence has been found
				if (!seqAllFromNode.isEmpty()){
					// Add all the sequence to the vector of graph sequences
					for (int j = 0; j < seqAllFromNode.size(); j++) {
						seqAllInGraph.add(seqAllFromNode.get(j));
					}
				}
			}
		}
		// Check for failure
		if (seqAllInGraph.isEmpty()) {
			int[] a = new int[seqLen];
			
			a[0] = -1;
			for(int i = 1; i < seqLen; i++) 
				a[i] = 0;
			
			seqAllInGraph.add(a);
		}
		return seqAllInGraph;
	}
}